home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS 1.31 / h / PCCTSAST.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-10  |  15.0 KB  |  634 lines  |  [TEXT/MPS ]
  1. /*
  2.  * PCCTSAST.C
  3.  *
  4.  * SOFTWARE RIGHTS
  5.  *
  6.  * We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
  7.  * domain.  An individual or company may do whatever they wish with
  8.  * source code distributed with SORCERER or the code generated by
  9.  * SORCERER, including the incorporation of SORCERER, or its output, into
  10.  * commerical software.
  11.  * 
  12.  * We encourage users to develop software with SORCERER.  However, we do
  13.  * ask that credit is given to us for developing SORCERER.  By "credit",
  14.  * we mean that if you incorporate our source code into one of your
  15.  * programs (commercial product, research project, or otherwise) that you
  16.  * acknowledge this fact somewhere in the documentation, research report,
  17.  * etc...  If you like SORCERER and have developed a nice tool with the
  18.  * output, please mention that you developed it using SORCERER.  In
  19.  * addition, we ask that this header remain intact in our source code.
  20.  * As long as these guidelines are kept, we expect to continue enhancing
  21.  * this system and expect to make other tools available as they are
  22.  * completed.
  23.  *
  24.  * SORCERER 1.00B13
  25.  * Terence Parr
  26.  * Parr Research Corporation
  27.  * AHPCRC, University of Minnesota
  28.  * 1992-1995
  29.  */
  30. #include "PCCTSAST.h"
  31. #include <stdarg.h>
  32. #include <ctype.h>
  33. #include "List.h"
  34.  
  35.                /* String Scanning/Parsing Stuff */
  36.  
  37. char *PCCTS_AST::scan_token_tbl[] = {
  38.     "invalid",    /*    0 */
  39.     "LPAREN",    /*    1 */
  40.     "RPAREN",    /*    2 */
  41.     "PERCENT",    /*    3 */
  42.     "INT",        /*    4 */
  43.     "COLON",    /*    5 */
  44.     "POUND",    /*    6 */
  45.     "PERIOD",    /*    7 */
  46. };
  47.  
  48. void PCCTS_AST::
  49. addChild(PCCTS_AST *t)
  50. {
  51.     if ( t==NULL ) return;
  52.     PCCTS_AST *s = (PCCTS_AST *)down();
  53.     if ( s!=NULL )
  54.     {
  55.         while ( s->right()!=NULL ) s = s->right();
  56.         s->setRight(t);
  57.     }
  58.     else
  59.         this->setDown(t);
  60. }
  61.  
  62. void PCCTS_AST::
  63. lisp(FILE *f)
  64. {
  65.     if ( down() != NULL ) fprintf(f," (");
  66.     lisp_action(f);
  67.     if ( down()!=NULL ) down()->lisp(f);
  68.     if ( down() != NULL ) fprintf(f," )");
  69.     if ( right()!=NULL ) right()->lisp(f);
  70. }
  71.  
  72. /* build a tree (root child1 child2 ... NULL)
  73.  * If root is NULL, simply make the children siblings and return ptr
  74.  * to 1st sibling (child1).  If root is not single node, return NULL.
  75.  *
  76.  * Siblings that are actually sibling lists themselves are handled
  77.  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
  78.  * in the tree ( NULL A B C D ).
  79.  *
  80.  * Requires at least two parameters with the last one being NULL.  If
  81.  * both are NULL, return NULL.
  82.  *
  83.  * The down() and right() down/right pointers are used to make the tree.
  84.  */
  85. PCCTS_AST *PCCTS_AST::
  86. make(PCCTS_AST *rt, ...)
  87. {
  88.     va_list ap;
  89.     register PCCTS_AST *child, *sibling=NULL, *tail, *w;
  90.     PCCTS_AST *root;
  91.  
  92.     va_start(ap, rt);
  93.     root = rt;
  94.  
  95.     if ( root != NULL )
  96.         if ( root->down() != NULL ) return NULL;
  97.     child = va_arg(ap, PCCTS_AST *);
  98.     while ( child != NULL )
  99.     {
  100.         /* find end of child */
  101.         for (w=child; w->right()!=NULL; w=w->right()) {;}
  102.         if ( sibling == NULL ) {sibling = child; tail = w;}
  103.         else {tail->setRight(child); tail = w;}
  104.         child = va_arg(ap, PCCTS_AST *);
  105.     }
  106.     if ( root==NULL ) root = sibling;
  107.     else root->setDown(sibling);
  108.     va_end(ap);
  109.     return root;
  110. }
  111.  
  112. /* The following push and pop routines are only used by ast_find_all() */
  113.  
  114. void PCCTS_AST::
  115. _push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
  116. {
  117.     (*sp)--;
  118.     require((*sp)>=0, "stack overflow");
  119.     st[(*sp)] = e;
  120. }
  121.  
  122. PCCTS_AST *PCCTS_AST::
  123. _pop(PCCTS_AST **st, int *sp)
  124. {
  125.     PCCTS_AST *e = st[*sp];
  126.     (*sp)++;
  127.     require((*sp)<=MaxTreeStackDepth, "stack underflow");
  128.     return e;
  129. }
  130.  
  131. #ifdef OLD
  132. void PCCTS_AST::
  133. addChild(PCCTS_AST *c)
  134. {
  135.     ASTBase *child = (ASTBase *)this->down();
  136.     ASTBase *prev = NULL;
  137.  
  138.     while ( child!=NULL )
  139.     {
  140.         prev = child;
  141.         child = (ASTBase *)child->right();
  142.     }
  143.  
  144.     if ( prev==NULL )    // must not be any children
  145.         this->setDown(c);
  146.     else
  147.         prev->setRight(c);
  148. }
  149. #endif
  150.  
  151. /* Find all occurrences of u in t.
  152.  * 'cursor' must be initialized to 't'.  It eventually
  153.  * returns NULL when no more occurrences of 'u' are found.
  154.  */
  155. PCCTS_AST *PCCTS_AST::
  156. find_all(PCCTS_AST *t, PCCTS_AST *u, PCCTS_AST **cursor)
  157. {
  158.     PCCTS_AST *sib;
  159.     static PCCTS_AST *template_stack[MaxTreeStackDepth];
  160.     static int tsp = MaxTreeStackDepth;
  161.     static int nesting = 0;
  162.  
  163.     if ( *cursor == NULL ) return NULL;
  164.     if ( *cursor!=t ) sib = *cursor;
  165.     else {
  166.         /* else, first time--start at top of template 't' */
  167.         tsp = MaxTreeStackDepth;
  168.         sib = t;
  169.         /* bottom of stack is always a NULL--"cookie" indicates "done" */
  170.         _push(template_stack, &tsp, NULL);
  171.     }
  172.  
  173. keep_looking:
  174.     if ( sib==NULL )    /* hit end of sibling list */
  175.     {
  176.         sib = _pop(template_stack, &tsp);
  177.         if ( sib == NULL ) { *cursor = NULL; return NULL; }
  178.     }
  179.  
  180.     if ( sib->token != u->token )
  181.     {
  182.         /* look for another match */
  183.         if ( sib->down()!=NULL )
  184.         {
  185.             if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
  186.             sib=sib->down();
  187.             goto keep_looking;
  188.         }
  189.         /* nothing below to try, try next sibling */
  190.         sib=sib->right();
  191.         goto keep_looking;
  192.     }
  193.  
  194.     /* found a matching root node, try to match what's below */
  195.     if ( match_partial(sib, u) )
  196.     {
  197.         /* record sibling cursor so we can pick up next from there */
  198.         if ( sib->down()!=NULL )
  199.         {
  200.             if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
  201.             *cursor = sib->down();
  202.         }
  203.         else if ( sib->right()!=NULL ) *cursor = sib->right();
  204.         else *cursor = _pop(template_stack, &tsp);
  205.         return sib;
  206.     }
  207.  
  208.     /* no match, keep searching */
  209.     if ( sib->down()!=NULL )
  210.     {
  211.         if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
  212.         sib=sib->down();
  213.     }
  214.     else sib = sib->right();    /* else, try to right if zip below */
  215.     goto keep_looking;
  216. }
  217.  
  218. /* are two trees exactly alike? */
  219. int PCCTS_AST::
  220. match(PCCTS_AST *t, PCCTS_AST *u)
  221. {
  222.     PCCTS_AST *sib;
  223.  
  224.     if ( t==NULL ) if ( u!=NULL ) return 0; else return 1;
  225.     if ( u==NULL ) return 0;
  226.  
  227.     for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
  228.     {
  229.         if ( sib->token != u->token ) return 0;
  230.         if ( sib->down()!=NULL )
  231.             if ( !match(sib->down(), u->down()) ) return 0;
  232.     }
  233.     return 1;
  234. }
  235.  
  236. /* Is 'u' a subtree of 't' beginning at the root? */
  237. int PCCTS_AST::
  238. match_partial(PCCTS_AST *t, PCCTS_AST *u)
  239. {
  240.     PCCTS_AST *sib;
  241.  
  242.     if ( u==NULL ) return 1;
  243.     if ( t==NULL ) if ( u!=NULL ) return 0; else return 1;
  244.  
  245.     for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
  246.     {
  247.         if ( sib->token != u->token ) return 0;
  248.         if ( sib->down()!=NULL )
  249.             if ( !match_partial(sib->down(), u->down()) ) return 0;
  250.     }
  251.     return 1;
  252. }
  253.  
  254. /* Walk the template tree 't' (matching against 'this'), filling in the
  255.  * 'labels' array, and setting 'n' according to how many labels were matched.
  256.  */
  257. int PCCTS_AST::
  258. scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
  259. {
  260.     ScanAST *sib;
  261.     PCCTS_AST *u = this;
  262.  
  263.     if ( u==NULL ) return 0;
  264.  
  265.     for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right, u=u->right())
  266.     {
  267.         /* make sure tokens match; token of '0' means wildcard match */
  268.         if ( sib->token != u->token() && sib->token!=0 ) return 0;
  269.         /* we have a matched token here; set label pointers if exists */
  270.         if ( sib->label_num>0 )
  271.         {
  272.             require(labels!=NULL, "label found in template, but no array of labels");
  273.             (*n)++;
  274.             *(labels[sib->label_num-1]) = u;
  275.         }
  276.         /* match what's below if something there and current node is not wildcard */
  277.         if ( sib->down!=NULL && sib->token!=0 )
  278.         {
  279.             if ( sib->down==NULL ) if ( u->down()!=NULL ) return 0; else return 1;
  280.             if ( !u->down()->scanmatch(sib->down, labels, n) ) return 0;
  281.         }
  282.     }
  283.     return 1;
  284. }
  285.  
  286. void PCCTS_AST::
  287. insert_after(PCCTS_AST *a, PCCTS_AST *b)
  288. {
  289.     PCCTS_AST *end;
  290.     require(a!=NULL, "insert_after: NULL input tree");
  291.     if ( b==NULL ) return;
  292.     /* find end of b's child list */
  293.     for (end=b; end->right()!=NULL; end=end->right()) {;}
  294.     end->setRight(a->right());
  295.     a->setRight(b);
  296. }
  297.  
  298. void PCCTS_AST::
  299. append(PCCTS_AST *a, PCCTS_AST *b)
  300. {
  301.     PCCTS_AST *end;
  302.     require(a!=NULL&&b!=NULL, "append: NULL input tree");
  303.     /* find end of child list */
  304.     for (end=a; end->right()!=NULL; end=end->right()) {;}
  305.     end->setRight(b);
  306. }
  307.  
  308. PCCTS_AST *PCCTS_AST::
  309. tail(PCCTS_AST *a)
  310. {
  311.     PCCTS_AST *end;
  312.     require(a!=NULL, "tail: NULL input tree");
  313.     /* find end of child list */
  314.     for (end=a; end->right()!=NULL; end=end->right()) {;}
  315.     return end;
  316. }
  317.  
  318. PCCTS_AST *PCCTS_AST::
  319. bottom(PCCTS_AST *a)
  320. {
  321.     PCCTS_AST *end;
  322.     require(a!=NULL, "bottom: NULL input tree");
  323.     /* find end of child list */
  324.     for (end=a; end->down()!=NULL; end=end->down()) {;}
  325.     return end;
  326. }
  327.  
  328. PCCTS_AST *PCCTS_AST::
  329. cut_between(PCCTS_AST *a, PCCTS_AST *b)
  330. {
  331.     PCCTS_AST *end, *ret;
  332.     require(a!=NULL&&b!=NULL, "cut_between: NULL input tree");
  333.     /* find node pointing to b */
  334.     for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
  335.         {;}
  336.     require(end->right()!=NULL, "ast_cut_between: a,b not connected");
  337.     end->setRight(NULL);    /* don't want it point to 'b' anymore */
  338.     ret = a->right();
  339.     a->setRight(b);
  340.     return ret;
  341. }
  342.  
  343. List *PCCTS_AST::
  344. to_slist(PCCTS_AST *t)
  345. {
  346.     List *list = new List;
  347.     PCCTS_AST *p;
  348.  
  349.     for (p=t; p!=NULL; p=p->right())
  350.     {
  351.         list->add(p);
  352.     }
  353.     return list;
  354. }
  355.  
  356. void PCCTS_AST::
  357. tfree(PCCTS_AST *t)
  358. {
  359.     if ( t == NULL ) return;
  360.     tfree( t->down() );
  361.     tfree( t->right() );
  362.     free( t );
  363. }
  364.  
  365. int PCCTS_AST::
  366. nsiblings(PCCTS_AST *t)
  367. {
  368.     int n=0;
  369.  
  370.     while ( t!=NULL )
  371.     {
  372.         n++;
  373.         t = t->right();
  374.     }
  375.     return n;
  376. }
  377.  
  378. PCCTS_AST *PCCTS_AST::
  379. sibling_index(PCCTS_AST *t, int i)
  380. {
  381.     int j=1;
  382.     require(i>=0, "sibling_index: i<0");
  383.  
  384.     while ( t!=NULL )
  385.     {
  386.         if ( j==i ) return t;
  387.         j++;
  388.         t = t->right();
  389.     }
  390.     return NULL;
  391. }
  392.  
  393. void PCCTS_AST::
  394. scanast_free(ScanAST *t)
  395. {
  396.     if ( t == NULL ) return;
  397.     scanast_free( t->down );
  398.     scanast_free( t->right );
  399.     free( t );
  400. }
  401.  
  402. /*
  403.  * scan
  404.  *
  405.  * This function is like scanf(): it attempts to match a template
  406.  * against an input tree.  A variable number of tree pointers
  407.  * may be set according to the '%i' labels in the template string.
  408.  * For example:
  409.  *
  410.  *   ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
  411.  *            t, &w, &x, &y, &z);
  412.  *
  413.  * Naturally, you'd want this converted from
  414.  *
  415.  *     ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
  416.  *              t, &w, &x, &y, &z);
  417.  *
  418.  * by SORCERER.
  419.  *
  420.  * This function call must be done withing a SORCERER file because SORCERER
  421.  * must convert the token references to the associated token number.
  422.  *
  423.  * This functions parses the template and creates trees which are then
  424.  * matched against the input tree.  The labels are set as they are
  425.  * encountered; hence, partial matches may leave some pointers set
  426.  * and some NULL.  This routines initializes all argument pointers to NULL
  427.  * at the beginning.
  428.  *
  429.  * This function returns the number of labels matched.
  430.  */
  431. int PCCTS_AST::
  432. ast_scan(char *templ, ...)
  433. {
  434.     va_list ap;
  435.     ScanAST *t;
  436.     int n, i, found=0;
  437.     PCCTS_AST ***label_ptrs=NULL;
  438.  
  439.     va_start(ap, templ);
  440.  
  441.     /* make a ScanAST tree out of the template */
  442.     t = stringparser_parse_scanast(templ, &n);
  443.  
  444.     /* make an array out of the labels */
  445.     if ( n>0 )
  446.     {
  447.         label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **));
  448.         require(label_ptrs!=NULL, "scan: out of memory");
  449.         for (i=1; i<=n; i++)
  450.         {
  451.             label_ptrs[i-1] = va_arg(ap, PCCTS_AST **);
  452.             *(label_ptrs[i-1]) = NULL;
  453.         }
  454.     }
  455.  
  456.     /* match the input tree against the template */
  457.     scanmatch(t, label_ptrs, &found);
  458.  
  459.     scanast_free(t);
  460.     free(label_ptrs);
  461.  
  462.     return found;
  463. }
  464.  
  465. ScanAST *PCCTS_AST::
  466. new_scanast(int tok)
  467. {
  468.     ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
  469.     if ( p == NULL ) {fprintf(stderr, "out of mem\n"); exit(-1);}
  470.     p->token = tok;
  471.     return p;
  472. }
  473.  
  474. ScanAST *PCCTS_AST::
  475. stringparser_parse_scanast(char *templ, int *num_labels)
  476. {
  477.     StringLexer lex;
  478.     StringParser parser;
  479.     ScanAST *t;
  480.  
  481.     stringlexer_init(&lex, templ);
  482.     stringparser_init(&parser, &lex);
  483.     t = stringparser_parse_tree(&parser);
  484.     *num_labels = parser.num_labels;
  485.     return t;
  486. }
  487.  
  488. void PCCTS_AST::
  489. stringparser_match(StringParser *parser, int token)
  490. {
  491.     if ( parser->token != token ) panic("bad tree in scan()");
  492. }
  493.  
  494. /*
  495.  * Match a tree of the form:
  496.  *        (root child1 child2 ... childn)
  497.  * or,
  498.  *        node
  499.  *
  500.  * where the elements are integers or labeled integers.
  501.  */
  502. ScanAST *PCCTS_AST::
  503. stringparser_parse_tree(StringParser *parser)
  504. {
  505.     ScanAST *t=NULL, *root, *child, *last;
  506.  
  507.     if ( parser->token != POUND )
  508.     {
  509.         return stringparser_parse_element(parser);
  510.     }
  511.     stringparser_match(parser,POUND);
  512.     parser->token = stringscan_gettok(parser->lexer);
  513.     stringparser_match(parser,LPAREN);
  514.     parser->token = stringscan_gettok(parser->lexer);
  515.     root = stringparser_parse_element(parser);
  516.     while ( parser->token != RPAREN )
  517.     {
  518.         child = stringparser_parse_element(parser);
  519.         if ( t==NULL ) { t = child; last = t; }
  520.         else { last->right = child; last = child; }
  521.     }
  522.     stringparser_match(parser,RPAREN);
  523.     parser->token = stringscan_gettok(parser->lexer);
  524.     root->down = t;
  525.     return root;
  526. }
  527.  
  528. ScanAST *PCCTS_AST::
  529. stringparser_parse_element(StringParser *parser)
  530. {
  531.     static char ebuf[100];
  532.     int label = 0;
  533.  
  534.     if ( parser->token == POUND )
  535.     {
  536.         return stringparser_parse_tree(parser);
  537.     }
  538.     if ( parser->token == PERCENT )
  539.     {
  540.         parser->token = stringscan_gettok(parser->lexer);
  541.         stringparser_match(parser,INT);
  542.         label = atoi(parser->lexer->text);
  543.         parser->num_labels++;
  544.         if ( label==0 ) panic("%%0 is an invalid label");
  545.         parser->token = stringscan_gettok(parser->lexer);
  546.         stringparser_match(parser,COLON);
  547.         parser->token = stringscan_gettok(parser->lexer);
  548.         /* can label tokens and wildcards */
  549.         if ( parser->token != INT && parser->token != PERIOD )
  550.             panic("can only label tokens");
  551.     }
  552.     if ( parser->token == INT )
  553.     {
  554.         ScanAST *p = new_scanast(atoi(parser->lexer->text));
  555.         parser->token = stringscan_gettok(parser->lexer);
  556.         p->label_num = label;
  557.         return p;
  558.     }
  559.     if ( parser->token == PERIOD )
  560.     {
  561.         ScanAST *p = new_scanast(0);    /* token of 0 is wildcard */
  562.         parser->token = stringscan_gettok(parser->lexer);
  563.         p->label_num = label;
  564.         return p;
  565.     }
  566.     sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token));
  567.     panic(ebuf);
  568. }
  569.  
  570. void PCCTS_AST::
  571. stringparser_init(StringParser *parser, StringLexer *input)
  572. {
  573.     parser->lexer = input;
  574.     parser->token = stringscan_gettok(parser->lexer);
  575.     parser->num_labels = 0;
  576. }
  577.  
  578. void PCCTS_AST::
  579. stringlexer_init(StringLexer *scanner, char *input)
  580. {
  581.     scanner->text[0]='\0';
  582.     scanner->input = input;
  583.     scanner->p = input;
  584.     stringscan_advance(scanner);
  585. }
  586.  
  587. void PCCTS_AST::
  588. stringscan_advance(StringLexer *scanner)
  589. {
  590.     if ( *(scanner->p) == '\0' ) scanner->c = StringScanEOF;
  591.     scanner->c = *(scanner->p)++;
  592. }
  593.  
  594. int PCCTS_AST::
  595. stringscan_gettok(StringLexer *scanner)
  596. {
  597.     char *index = &scanner->text[0];
  598.     static char ebuf[100];
  599.  
  600.     while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
  601.     if ( isdigit(scanner->c) )
  602.     {
  603.         int tok = INT;
  604.         while ( isdigit(scanner->c) ) {
  605.             *index++ = scanner->c;
  606.             stringscan_advance(scanner);
  607.         }
  608.         *index = '\0';
  609.         return tok;
  610.     }
  611.     switch ( scanner->c )
  612.     {
  613.         case '#' : stringscan_advance(scanner); return POUND;
  614.         case '(' : stringscan_advance(scanner); return LPAREN;
  615.         case ')' : stringscan_advance(scanner); return RPAREN;
  616.         case '%' : stringscan_advance(scanner); return PERCENT;
  617.         case ':' : stringscan_advance(scanner); return COLON;
  618.         case '.' : stringscan_advance(scanner); return PERIOD;
  619.         case '\0' : return StringScanEOF;
  620.         case StringScanEOF : return StringScanEOF;
  621.         default  :
  622.             sprintf(ebuf, "invalid char in scan: '%c'", scanner->c);
  623.             panic(ebuf);
  624.     }
  625. }
  626.  
  627. char *PCCTS_AST::
  628. scan_token_str(int t)
  629. {
  630.     if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t];
  631.     else if ( t==StringScanEOF ) return "<end-of-string>";
  632.     else return "<invalid-token>";
  633. }
  634.